package A1_栈和队列;

import java.util.Deque;
import java.util.LinkedList;

public class LC_239滑动窗口最大值 {
    Deque<Integer> que=new LinkedList<>();
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==1)
            return nums;
        Deque<Integer> deque=new LinkedList<>();
        int[] res=new int[nums.length-k+1];//存放最大值
        int idx=0;
        for(int i=0;i<nums.length;i++){
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.poll();
            }
            // 2.维护单调递减队列：新元素若大于队尾元素，则弹出队尾元素，直到满足单调性
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offer(i);
            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }
    //弹出元素
    public void pop(int val){
        if(!que.isEmpty() && que.peekFirst()==val)
            que.pollFirst();
    }
    //放进元素，并且卷走前面所有小于这个数的元素
    public void push(int val){
        while(!que.isEmpty() && val>que.peekLast())
            que.pollLast();
        que.offerLast(val);
    }
    //获取最大值，此时首元素即是最大值
    public int getMaxValue(){
        return que.peekFirst();
    }
}
